package 题目集.动态规划.背包问题;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;

/**
 * 思路：枚举每个主键必须买下的最大值，用一个set记录下现有的主键
 * https://www.luogu.com.cn/problem/P1064
 * 注意：如果依赖是从前往后，则需要从前dfs，如果是从后往前，则需要从后dfs
 */
public class ch05_有依赖的背包 {
	static int sum, n;
	static PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
	static int[] w, v, pre;
	static boolean[] vis;

	public static void main(String[] args) {
		Reader sc = new Reader();
		sum = sc.nextInt();
		n = sc.nextInt();
		w = new int[n + 1];
		v = new int[n + 1];
		pre = new int[n + 1];
		vis = new boolean[n + 1];
		vis[0] = true;
		for (int i = 1; i <= n; i++) {
			w[i] = sc.nextInt();
			v[i] = sc.nextInt();
			pre[i] = sc.nextInt();
		}
		int res = dfs(1, sum);
		pw.println(res);
		pw.flush();
	}
	//从前往后dfs
	public static int dfs(int i,int sum){
		if (i>n) return 0;
		int nochose=dfs(i+1,sum);
		int chose=0;
		if (sum>=w[i]&&vis[pre[i]]){	//能拿下，且前置条件已处理
			vis[i]=true;
			chose=dfs(i+1,sum-w[i])+w[i]*v[i];
			vis[i]=false;
		}
		return Math.max(chose,nochose);
	}
//	static int dfs(int i, int sum) {
//		if (i == 0) {
//			return 0;
//		}
//		int nochose = dfs(i - 1, sum);
//		int chose = 0;
//		if (sum >= w[i] && vis[pre[i]]) {	//能拿下，且前置条件已处理
//			vis[i]=true;
//			chose = dfs(i - 1, sum - w[i]) + w[i] * v[i];
//			vis[i]=false;
//		}
//		return Math.max(chose, nochose);	//拿当前和不拿当前
//	}

	/**
	 * 2000 10
	 *
	 * 1 500 1 0
	 * 2 400 4 0 *
	 * 3 300 5 1
	 * 4 400 5 1
	 * 5 200 5 0 *
	 * 6 500 4 5 *
	 * 7 400 4 0 *
	 * 320 2 0
	 * 410 3 0 *
	 * 400 3 5
	 */
	static class Reader {
		private StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

		public int nextInt() {
			try {
				in.nextToken();
			} catch (Exception e) {
			}
			return (int) in.nval;
		}
	}
}
